序言

编辑：詹好，赵志民，王茂霖

关于《机器学习理论导引》

近年来，机器学习领域发展迅猛，相关的课程与教材层出不穷。国内的经典教材如周志华的 《机器学习》 和李航的 《统计学习方法》，为许多学子提供了机器学习的入门指引。而在国外，Mitchell 的 Machine Learning、Duda 等人的 Pattern Classification、Alpaydin 的 Introduction to Machine Learning 等书籍则提供了更为系统的学习路径。对于希望深入学习的读者，Bishop 的 Pattern Recognition and Machine Learning、Murphy 的 Machine Learning - A Probabilistic Perspective、Hastie 等人的 The Elements of Statistical Learning 等著作也能提供详尽的理论指导。这些书籍无论在国内外，都成为了学习机器学习的重要资源。

然而，从机器学习理论的角度来看，现有的学习材料仍存在不足之处。相比于聚焦机器学习算法的著作，专注于机器学习理论的书籍未得到足够的重视。尽管上述一些经典著作中涉及到理论探讨，但篇幅有限，往往仅以独立章节或片段呈现，难以满足深入研究的需求。

以往的机器学习理论经典教材大多为英文撰写。上世纪末围绕统计学习理论展开的讨论，催生了诸如 Vapnik 的 The Nature of Statistical Learning Theory 和 Statistical Learning Theory，以及 Devroye 等人的 A Probabilistic Theory of Pattern Recognition 等经典文献。近年来，Shalev-Shwartz 和 Ben-David 的 Understanding Machine Learning，以及 Mohri 等人的 Foundations of Machine Learning 进一步推进了这一领域的发展。虽然部分经典著作已有高质量的中文译本，但由中文作者撰写的机器学习理论入门书籍仍显不足。

如今，周志华、王魏、高尉、张利军等老师合著的 《机器学习理论导引》（以下简称《导引》）填补了这一空白。该书以通俗易懂的语言，为有志于学习和研究机器学习理论的读者提供了良好的入门指引。全书涵盖了 可学性、假设空间复杂度、泛化界、稳定性、一致性、收敛率、遗憾界 七个重要的概念和理论工具。

尽管学习机器学习理论可能不像学习算法那样能够立即应用，但只要持之以恒，深入探究，必将能够领悟到机器学习中的重要思想，并体会其中的深邃奥妙。

-- 詹好

关于《机器学习理论导引》讲解笔记

《导引》的讲解笔记在团队内部被亲切地称为《钥匙书》。“钥匙”寓意着帮助读者开启知识之门，解答学习中的疑惑。

《导引》作为一本理论性较强的著作，涵盖了大量数学定理和证明。尽管作者团队已尽力降低学习难度，但由于机器学习理论本身的复杂性，读者仍需具备较高的数学基础。这可能导致部分读者在学习过程中感到困惑，影响学习效果。此外，由于篇幅限制，书中对某些概念和理论的实例说明不足，也增加了理解的难度。

基于以上原因，我们决定编辑这本《钥匙书》作为参考笔记，对《导引》进行深入的注解和补充。其目的是帮助读者更快理解并掌握书中内容，同时记录我们在学习过程中的思考和心得。

《钥匙书》主要包含以下四个部分：

1. 概念解释：介绍书中涉及但未详细阐释的相关概念。
2. 证明补充：详细解释部分证明的思路，并补充书中省略的证明过程。
3. 案例分享：增加相关实例，帮助读者加深对抽象概念的理解。

鉴于《导引》第一章的内容简明易懂，《钥匙书》从第二章开始详细展开。

对我个人而言，《机器学习理论导引》与Understanding Machine Learning和Foundations of Machine Learning一样，都是既“无用”又“有用”的书籍。“无用”在于目前的经典机器学习理论尚难全面解释深度学习，尤其是现代生成式大模型的惊人表现。然而，我坚信未来的理论突破将基于现有研究成果，开创新的篇章。因此，分析结论可能并非最重要，真正宝贵的是其中蕴含的思想和分析思路。数学作为一种强有力的工具，能够帮助我们更深入地理解和探索。我期望未来的深度学习能够拥有更多坚实的理论支撑，从而更好地指导实践。正如费曼所言：“What I cannot create, I do not understand.”——“凡我不能创造，我就不能理解。”希望大家能从这些理论中获得启发，创造出更有意义的成果。

另一方面，这本书也让我认识到自身的不足。不同于传统的机器学习算法教材，本书要求读者具备良好的数学功底，通过数学工具从更抽象的角度分析机器学习算法的性质，而非算法本身。学习之路或许漫长，但正如《牧羊少年的奇幻漂流》中所言：“每个人的寻梦过程都是以‘新手的运气’为开端，又总是以‘对远征者的考验’收尾。”希望大家能坚持经历考验，最终实现自己的梦想。

自《钥匙书》v1.0 版本发布以来，受到了众多学习者的关注。我们也收到了许多关于教材内容的疑问。为进一步深入理解相关知识，并记录团队对机器学习理论相关书籍的学习过程，我们将持续对《钥匙书》进行不定期更新，期待大家的关注。

-- 王茂霖

关于机器学习理论与实践

随着机器学习的蓬勃发展，**SOTA（State-of-the-art，最先进技术）**几乎成了评判算法优劣的唯一标准。这种对表面表现的单一追求，常常忽视了支撑其背后的基础理论。正如硅谷投资人吴军曾指出的，最顶尖的科学家通过理论设定学科的边界，赋予未来研究者方向和框架。1936年，图灵在其著名的论文中为可计算性理论奠定了基础，定义了哪些问题可以通过算法解决。同样，机器学习领域的研究者只有具备深厚的理论根基，才能在实践中面对瓶颈时不至于迷失，而是继续探索，甚至开拓新的领域。

**没有免费午餐定理（No Free Lunch Theorem）**便是一个鲜明的例子。该定理告诉我们，不存在一种能够应对所有问题的通用算法。尽管许多算法在特定领域或时间点看似“无敌”，如神经网络的兴起，但每个算法的优势往往局限于特定的任务和环境。因此，过度依赖某一种算法的短期成功，可能导致长期陷入困境。通过理论学习，研究者能够意识到这种局限，并避免在实践中过分追逐SOTA，而忽视更为长远的技术路线。

当然，理论和实践之间的差距依然存在。许多理论假设在现实应用中并不完全成立，尤其是在面对大数据和复杂模型时，理论的指导可能显得力不从心。但这并不意味着理论无用，恰恰相反，这正是学科发展的驱动力。正如机器学习的发展史所示，当实践进展遇到瓶颈时，往往是理论创新引领了新的突破。例如，在早期，受限于数据和算力，机器学习中的理论研究主导了整个领域的发展；而到了互联网时代，随着数据量的指数级增长和计算资源的提升，实践逐渐超越了理论。如今，面对数据、能源和算力等问题的挑战，理论又重新成为了优化模型效率和算法性能的焦点。

一个鲜明的例子是，近期在 ICLR 2024 大会上，斯隆奖得主马腾宇及其团队通过数学方法证明了Transformer 模型具备模拟任意多项式规模数字电路的能力。这一成果表明，随着**思维链（Chain of Thought, CoT）的不断延展，Transformer能够有效地处理更为复杂的问题。 这项研究不仅展示了理论在推动前沿技术进步中的重要性，还让我们认识到，尽管外界对数据质量不足、模型的算力需求以及能源消耗提出了诸多质疑，但这些问题并非不可逾越。通过深入学习机器学习理论，我们可以更好地理解这些挑战，意识到它们实际上是迈向通用人工智能（AGI）**过程中必须面对和解决的关键节点。

不仅如此，理论学习还有助于我们建立对算法泛化能力的深刻理解。通过对机器学习理论的深入研究，我们能够推导出在不同假设条件下，算法的性能极限。比如，我们可以评估某一算法的收敛速度，预测其在不同数据量和模型复杂度下的表现。这些理论工具不仅提高了研究的严谨性，还为实际应用提供了有力的指导。例如，正是通过理论推导，我们能够理解大规模语言模型的训练为何需要如此庞大的数据集，同时又能预见在某些任务上微调模型的效果。

最后，掌握机器学习理论不仅能够为初学者奠定坚实的基础，增强他们的信心，还能帮助他们在面对外界质疑时保持理性和清醒的判断。无论是在研究中追求算法的提升，还是在实践中应对现实的挑战，理论的力量都不可或缺。在本书的编撰中，我们特别对部分证明进行了必要的诠释和展开，主要集中在原书中存在流畅性不足的内容，或那些虽提供了参考文献但证明篇幅不超过5页的论述。对于超出5页的文献，我们建议读者直接参阅原文，以便进行更深入的探究；此类情况在本书中出现频率较低，约不超过五处。

-- 赵志民

项目成员贡献与特别鸣谢

詹好负责了项目的初期规划与统筹，并参与了第一版的编辑和审核；赵志民主导了项目二期的更新与维护，并负责全书最终编辑和校验；李一飞参与了第1-5章内容的编辑；王茂霖参与了第2-6章内容的编辑。

另外，特别鸣谢了谢文睿和杨昱文，他们共同提供了本书的在线阅读功能；张雨对第2章的早期内容进行了修订，各成员的协作确保了本书高质量的编写和顺利完成。

主要符号表

$x$ 标量
$x$ 向量
$A$ 矩阵
$I$ 单位阵
$\mathcal{X}$ 样本空间或状态空间
$\mathcal{H}$ 假设空间
$\mathcal{D}$ 概率分布
$D$ 数据样本(数据集)
$\mathbb{R}$ 实数集
$\mathbb{R}^+$ 正实数集
$\mathfrak{L}$ 学习算法
$(·,·,·)$ 行向量
$(;,;,)$ 列向量
$(·)^T$ 向量或矩阵转置
${\cdots}$ 集合
$[m]$ 集合 $\{1,\dots,m\}$
$|{\cdots}|$ 集合 ${\cdots}$ 中元素的个数
$\|·\|_p$ 范数, $p$ 缺省时为 $L_2$ 范数
$P()$, $P(·|·)$ 概率质量函数, 条件概率质量函数
$p(·)$, $p(·|·)$ 概率密度函数, 条件概率密度函数
$E_{.~\mathcal{D}}[f(·)]$ 函数 $f(·)$ 对 $·$ 在分布 $D$ 下的数学期望, 意义明确时将省略 $D$ 和(或)$·$
$\sup(·)$ 上确界
$\inf(·)$ 下确界
$\mathbb{I}(·)$ 指示函数, 在 $·$ 为真和假时分别取值为 $1, 0$
$\text{sign}(·)$ 符号函数, 在 $·<0,=0,>0$ 时分别取值为 $-1, 0, 1$

第1章：预备定理

编辑：赵志民, 李一飞

本章将对书中出现或用到的重要定理进行回顾，并简要解释其证明和应用场景。对于可能不熟悉相关基础知识的读者，建议参考附录中的基础知识部分。通过这些定理的阐述，希望帮助读者更好地理解数学推导的核心原理，并为后续章节的学习打下坚实基础。大数定律（Law of Large Numbers）和集中不等式（Concentration Inequality）密切相关，二者共同揭示了随机变量偏离其期望值的行为。大数定律说明，当样本量足够大时，样本均值会以概率收敛于总体的期望值，反映了长期平均结果的稳定性。而集中不等式（定理 1.8 至 1.18）则更进一步，为随机变量在有限样本量下偏离其期望值的可能性提供了精确的上界。这些不等式描述了随机变量偏离期望值的程度有多大，通过对概率的约束，确保这种偏离发生的概率较小，从而为各种随机现象提供了更细致的控制。集中不等式在大数定律的基础上提供了有力的工具，用于分析有限样本中的波动。

1.1 Jensen 不等式

对于任意凸函数 $f$，则有：

$$\begin{equation} f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)] \end{equation}$$

成立。

证明

设 $p(x)$ 为 $X$ 的概率密度函数。由 Taylor 展开式及 $f$ 的凸性，可知 $\exists \xi$ 使得：

$$\begin{equation} \begin{align*} f(x) &= f(\mathbb{E}[X]) + f^{\prime}(\mathbb{E}[X])(x-\mathbb{E}[X]) + \frac{f^{\prime \prime}(\xi)}{2}(x-\mathbb{E}[X])^{2} \\ & \geq f(\mathbb{E}[X]) + f^{\prime}(\mathbb{E}[X])(x-\mathbb{E}[X]) \end{align*} \end{equation}$$

对上式取期望，得到：

$$\begin{equation} \begin{align*} \mathbb{E}[f(X)] &= \int p(x) f(x) \,dx \\ &\geq f(\mathbb{E}[X]) \int p(x) \,dx + f^{\prime}(\mathbb{E}[X]) \int p(x)(x-\mathbb{E}[X]) \,dx \\ &= f(\mathbb{E}[X]) \end{align*} \end{equation}$$

因此，原不等式得证。

如果 $f$ 是凹函数，则 Jensen 不等式变为：

$$\begin{equation} f(\mathbb{E}[X]) \geq \mathbb{E}[f(X)] \end{equation}$$

这一结论可以通过将上述证明中的 $f$ 替换为 $-f$ 得到。$\square$

1.2 Hölder 不等式

对于任意 $p, q \in \mathbb{R}^{+}$，且满足 $\frac{1}{p} + \frac{1}{q} = 1$，则有：

$$\begin{equation} \mathbb{E}[|XY|] \leq (\mathbb{E}[|X|^p])^{\frac{1}{p}} (\mathbb{E}[|Y|^q])^{\frac{1}{q}} \end{equation}$$

成立。

证明

设 $f(x)$ 和 $g(y)$ 分别为 $X$ 和 $Y$ 的概率密度函数，定义：

$$\begin{equation} M = \frac{|x|}{(\int_X |x|^p f(x) \,dx)^{\frac{1}{p}}}, \quad N = \frac{|y|}{(\int_Y |y|^q g(y) \,dy)^{\frac{1}{q}}} \end{equation}$$

代入 Young 不等式：

$$\begin{equation} MN \leq \frac{1}{p}M^p + \frac{1}{q}N^q \end{equation}$$

对该不等式两边同时取期望：

$$\begin{equation} \begin{align*} \frac{\mathbb{E}[|XY|]}{(\mathbb{E}[|X|^p])^{\frac{1}{p}} (\mathbb{E}[|Y|^q])^{\frac{1}{q}}} &= \frac{\int_{XY} |xy| f(x)g(y) \,dx\,dy}{(\int_X |x|^p f(x) \,dx)^{\frac{1}{p}} (\int_Y |y|^q g(y) \,dy)^{\frac{1}{q}}} \\ &\leq \frac{\int_X |x|^p f(x) \,dx}{p \int_X |x|^p f(x) \,dx} + \frac{\int_Y |y|^q g(y) \,dy}{q \int_Y |y|^q g(y) \,dy} \\ &= \frac{1}{p} + \frac{1}{q} \\ &= 1 \end{align*} \end{equation}$$

因此，Hölder 不等式得证。$\square$

1.3 Cauchy-Schwarz 不等式

当 $p = q = 2$ 时，Hölder 不等式退化为 Cauchy-Schwarz 不等式：

$$\begin{equation} \mathbb{E}[|XY|] \leq \sqrt{\mathbb{E}[X^{2}] \cdot \mathbb{E}[Y^{2}]} \end{equation}$$

1.4 Lyapunov 不等式

对于任意 $0 \lt r \leq s$，有：

$$\begin{equation} \sqrt[r]{\mathbb{E}[|X|^{r}]} \leq \sqrt[s]{\mathbb{E}[|X|^{s}]} \end{equation}$$

证明

由 Hölder 不等式： 对任意 $p \geq 1$，有：

$$\begin{equation} \begin{align*} \mathbb{E}[|X|^{r}] &= \mathbb{E}[|X \cdot 1|^{r}] \\ &\leq (\mathbb{E}[|X|^{rp}])^{\frac{1}{p}} \cdot (\mathbb{E}[1^q])^{\frac{1}{q}} \\ &= (\mathbb{E}[|X|^{rp}])^{\frac{1}{p}} \end{align*} \end{equation}$$

记 $s = rp \geq r$，则：

$$\begin{equation} \mathbb{E}[|X|^{r}] \leq (\mathbb{E}[|X|^{s}])^{\frac{r}{s}} \end{equation}$$

因此，原不等式得证。$\square$

1.5 Minkowski 不等式

对于任意 $p \geq 1$，有：

$$\begin{equation} \sqrt[p]{\mathbb{E}[|X+Y|^p]} \leq \sqrt[p]{\mathbb{E}[|X|^p]} + \sqrt[p]{\mathbb{E}[|Y|^p]} \end{equation}$$

证明

由三角不等式和 Hölder 不等式，可得：

$$\begin{equation} \begin{align*} \mathbb{E}[|X+Y|^p] &\leq \mathbb{E}[(|X|+|Y|)|X+Y|^{p-1}] \\ &= \mathbb{E}[|X\|X+Y|^{p-1}] + \mathbb{E}[|Y\|X+Y|^{p-1}] \\ &\leq (\mathbb{E}[|X|^p])^{\frac{1}{p}} (\mathbb{E}[|X+Y|^{(p-1)q}])^{\frac{1}{q}} + (\mathbb{E}[|Y|^p])^{\frac{1}{p}} (\mathbb{E}[|X+Y|^{(p-1)q}])^{\frac{1}{q}} \\ &= [(\mathbb{E}[|X|^p])^{\frac{1}{p}} + (\mathbb{E}[|Y|^p])^{\frac{1}{p}}] \cdot \frac{\mathbb{E}[|X+Y|^p]}{(\mathbb{E}[|X+Y|^p])^{\frac{1}{p}}} \end{align*} \end{equation}$$

化简后即得证。$\square$

1.6 Bhatia-Davis 不等式

对 $X \in [a,b]$，有：

$$\begin{equation} \mathbb{V}[X] \leq (b - \mathbb{E}[X])(\mathbb{E}[X] - a) \leq \frac{(b-a)^2}{4} \end{equation}$$

证明

因为 $a \leq X \leq b$，所以有：

$$\begin{equation} \begin{align*} 0 &\leq \mathbb{E}[(b-X)(X-a)] \\ &= -\mathbb{E}[X^2] - ab + (a+b)\mathbb{E}[X] \end{align*} \end{equation}$$

因此，

$$\begin{equation} \begin{align*} \mathbb{V}[X] &= \mathbb{E}[X^2] - \mathbb{E}[X]^2 \\ &\leq -ab + (a+b)\mathbb{E}[X] - \mathbb{E}[X^2] \\ &= (b - \mathbb{E}[X])(\mathbb{E}[X] - a) \end{align*} \end{equation}$$

考虑 AM-GM 不等式：

$$\begin{equation} xy \leq (\frac{x+y}{2})^2 \end{equation}$$

将 $x = b - \mathbb{E}[X]$ 和 $y = \mathbb{E}[X] - a$ 带入并化简即得证。$\square$

1.7 Union Bound（Boole's）不等式

对于任意事件 $X$ 和 $Y$，有：

$$\begin{equation} P(X \cup Y) \leq P(X) + P(Y) \end{equation}$$

证明

根据概率的加法公式：

$$\begin{equation} P(X \cup Y) = P(X) + P(Y) - P(X \cap Y) \leq P(X) + P(Y) \end{equation}$$

由于 $P(X \cap Y) \geq 0$，因此不等式得证。$\square$

1.8 Markov 不等式

若 $X \geq 0$，则对于任意 $\varepsilon \gt 0$，有：

$$\begin{equation} P(X \geq \varepsilon) \leq \frac{\mathbb{E}[X]}{\varepsilon} \end{equation}$$

证明

由定义可得：

$$\begin{equation} \mathbb{E}[X] = \int_{0}^{\infty} x p(x) \,dx \geq \int_{\varepsilon}^{\infty} x p(x) \,dx \geq \varepsilon \int_{\varepsilon}^{\infty} p(x) \,dx = \varepsilon P(X \geq \varepsilon) \end{equation}$$

因此，原不等式得证。$\square$

1.9 Chebyshev 不等式

对于任意 $\varepsilon \gt 0$，有：

$$\begin{equation} P(|X-\mathbb{E}[X]| \geq \varepsilon) \leq \frac{\mathbb{V}[X]}{\varepsilon^{2}} \end{equation}$$

证明

利用 Markov 不等式，得到：

$$\begin{equation} P(|X-\mathbb{E}[X]| \geq \varepsilon) = P((X-\mathbb{E}[X])^2 \geq \varepsilon^{2}) \leq \frac{\mathbb{E}[(X-\mathbb{E}[X])^2]}{\varepsilon^{2}} = \frac{\mathbb{V}[X]}{\varepsilon^{2}} \end{equation}$$

因此，Chebyshev 不等式得证。$\square$

1.10 Cantelli 不等式

对于任意 $\varepsilon \gt 0$，有：

$$\begin{equation} P(X-\mathbb{E}[X] \geq \varepsilon) \leq \frac{\mathbb{V}[X]}{\mathbb{V}[X]+\varepsilon^{2}} \end{equation}$$

证明

设 $Y = X - \mathbb{E}[X]$，则对于任意 $\lambda \geq 0$，有：

$$\begin{equation} \begin{align*} P(X-\mathbb{E}[X] \geq \varepsilon) &= P(Y \geq \varepsilon) \\ &= P(Y+\lambda \geq \varepsilon+\lambda) \\ &= P((Y+\lambda)^{2} \geq (\varepsilon+\lambda)^{2}) \\ &\leq \frac{\mathbb{E}[(Y+\lambda)^{2}]}{(\varepsilon+\lambda)^{2}} = \frac{\mathbb{V}[X]+\lambda^{2}}{(\varepsilon+\lambda)^{2}} \end{align*} \end{equation}$$

通过对 $\lambda$ 求导，得右端在 $\lambda = \frac{\mathbb{V}[X]}{\varepsilon}$ 时取得最小值 $\frac{\mathbb{V}[X]}{\mathbb{V}[X]+\varepsilon^{2}}$，因此：

$$\begin{equation} P(X-\mathbb{E}[X] \geq \varepsilon) \leq \frac{\mathbb{V}[X]}{\mathbb{V}[X]+\varepsilon^{2}} \end{equation}$$

原不等式得证。$\square$

值得注意的是，Cantelli 不等式是 Chebyshev 不等式的加强版，也称为单边 Chebyshev 不等式。通过类似的构造方法，可以推导出比 Cantelli 不等式更严格的上界。

1.11 Chernoff 界（Chernoff-Cramér 界）

对于任意 $\lambda \gt 0, \varepsilon \gt 0$，有：

$$\begin{equation} P(X \geq \varepsilon) \leq \min_{\lambda \gt 0} \frac{\mathbb{E}[e^{\lambda X}]}{e^{\lambda \varepsilon}} \end{equation}$$

对于任意 $\lambda \lt 0, \varepsilon \gt 0$，有：

$$\begin{equation} P(X \leq \varepsilon) \leq \min_{\lambda \lt 0} \frac{\mathbb{E}[e^{\lambda X}]}{e^{\lambda \varepsilon}} \end{equation}$$

证明

应用 Markov 不等式，有：

$$\begin{equation} P(X \geq \varepsilon) = P(e^{\lambda X} \geq e^{\lambda \varepsilon}) \leq \frac{\mathbb{E}[e^{\lambda X}]}{e^{\lambda \varepsilon}}, \quad \lambda \gt 0, \varepsilon \gt 0 \end{equation}$$

同理，

$$\begin{equation} P(X \leq \varepsilon) = P(e^{\lambda X} \leq e^{\lambda \varepsilon}) \leq \frac{\mathbb{E}[e^{\lambda X}]}{e^{\lambda \varepsilon}}, \quad \lambda \lt 0, \varepsilon \gt 0 \end{equation}$$

因此，Chernoff 界得证。$\square$

基于上述 Chernoff 界的技术，我们可以进一步定义次高斯性：

定义 1 (随机变量的次高斯性)：若一个期望为零的随机变量 $X$ 的矩母函数满足 $\forall \lambda \in \mathbb{R}^+$：

$$\begin{equation} \mathbb{E}[e^{\lambda X}] \leq \exp(\frac{\sigma^2\lambda^2}{2}) \end{equation}$$

则称 $X$ 服从参数为 $\sigma$ 的次高斯分布。

实际上，Hoeffding 引理中的随机变量 $X$ 服从 $\frac{(b-a)}{2}$ 的次高斯分布。Hoeffding 引理也是次高斯分布的直接体现。次高斯性还有一系列等价定义，这里不作详细讨论。

次高斯分布有一个直接的性质：假设两个独立的随机变量 $X_1, X_2$ 都是次高斯分布的，分别服从参数 $\sigma_1, \sigma_2$，那么 $X_1 + X_2$ 就是服从参数为 $\sqrt{\sigma_1^2 + \sigma_2^2}$ 的次高斯分布。这个结果的证明可以直接利用定义来完成。

显然，并非所有常见的随机变量都是次高斯的，例如指数分布。为此可以扩大定义：

定义 2 (随机变量的次指数性)：若非负的随机变量 $X$ 的矩母函数满足 $\forall \lambda \in (0,a)$：

$$\begin{equation} \mathbb{E}[e^{\lambda X}] \leq \frac{a}{a - \lambda} \end{equation}$$

则称 $X$ 服从参数为 $(\mathbb{V}[X], 1/a)$ 的次指数分布。

同样地，次指数性也有一系列等价定义。一种不直观但更常用的定义如下：存在 $(\sigma^2, b)$，使得 $\forall |s| \lt 1/b$：

$$\begin{equation} \mathbb{E}[e^{s(X−\mathbb{E}[X])}] \leq \exp ( \frac{s^2\sigma^2}{2} ) \end{equation}$$

常见的次指数分布包括：指数分布，Gamma 分布，以及任何有界随机变量。

类似地，次指数分布对于加法也是封闭的：如果 $X_1, X_2$ 分别是服从 $(\sigma_1^2, b_1)$ 和 $(\sigma_2^2, b_2)$ 的次指数分布，那么 $X_1 + X_2$ 是服从 $(\sigma_1^2 + \sigma_2^2, \max(b_1, b_2))$ 的次指数分布。在高维统计问题中，次高斯分布和次指数分布的尾端控制能得到一些重要的结论。

1.12 Chernoff 不等式（乘积形式）

对于 $m$ 个独立同分布的随机变量 $x_i \in [0, 1], i \in [m]$，设 $X = \sum_{i=1}^m X_i$，$\mu \gt 0$ 且 $r \leq 1$。若对所有 $i \leq m$ 都有 $\mathbb{E}[x_i] \leq \mu$，则：

$$\begin{equation} \begin{align*} P(X \geq (1+r)\mu m) \leq e^{-\frac{r^2 \mu m}{3}}, \quad r \geq 0 \\ P(X \leq (1-r)\mu m) \leq e^{-\frac{r^2 \mu m}{2}}, \quad r \geq 0 \end{align*} \end{equation}$$

证明

应用 Markov 不等式，有：

$$\begin{equation} P(X \geq (1+r)\mu m) = P((1+r)^X \geq (1+r)^{(1+r)\mu m}) \leq \frac{\mathbb{E}[(1+r)^X]}{(1+r)^{(1+r)\mu m}} \end{equation}$$

由于 $x_i$ 之间是独立的，可得：

$$\begin{equation} \mathbb{E}[(1+r)^X] = \prod_{i=1}^m \mathbb{E}[(1+r)^{x_i}] \leq \prod_{i=1}^m \mathbb{E}[1+rx_i] \leq \prod_{i=1}^m (1+r\mu) \leq e^{r\mu m} \end{equation}$$

其中，第二步使用了 $\forall x \in [0,1]$ 都有 $(1+r)^x \leq 1+rx$，第三步使用了 $\mathbb{E}[x_i] \leq \mu$，第四步使用了 $\forall x \in [0,1]$ 都有 $1+x \leq e^x$。

又由于 $\forall r \in [0,1]$，有 $\frac{e^r}{(1+r)^{1+r}} \leq e^{-\frac{r^2}{3}}$，综上所述：

$$\begin{equation} P(X \geq (1+r)\mu m) \leq (\frac{e^r}{(1+r)^{(1+r)}})^{\mu m} \leq e^{-\frac{r^2 \mu m}{3}} \end{equation}$$

当我们将 $r$ 替换为 $-r$ 时，根据之前的推导，并利用 $\forall r \in [0,1]$ 有 $\frac{e^r}{(1-r)^{1-r}} \leq e^{-\frac{r^2}{2}}$，可得第二个不等式的证明。$\square$

1.13 最优 Chernoff 界

如果 $X$ 是一个随机变量，并且 $\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}] \leq e^{\phi(\lambda)}$ 对于所有 $\lambda \geq 0$ 成立，则有以下结论：

$$\begin{equation} P(X - \mathbb{E}X \geq \varepsilon) \leq e^{-\phi^*(\varepsilon)}, \quad \varepsilon \geq 0 \end{equation}$$

或

$$\begin{equation} P(X - \mathbb{E}X \leq (\phi^*)^{-1}(\ln(1/\delta))) \geq 1 - \delta, \quad \delta \in [0,1] \end{equation}$$

其中，$\phi^*$ 是 $\phi$ 的凸共轭函数，即 $\phi^*(x) = \sup_{\lambda \geq 0}(\lambda x - \phi(\lambda))$。

证明

根据 Chernoff 不等式，有：

$$\begin{equation} \begin{align*} P(X - \mathbb{E}X \geq \varepsilon) &\leq \inf_{\lambda \geq 0} e^{-\lambda \varepsilon} \mathbb{E}[e^{\lambda(X-\mathbb{E}X)}] \\ &\leq \inf_{\lambda \geq 0} e^{\phi(\lambda) - \lambda \varepsilon} \\ &= e^{-\sup_{\lambda \geq 0}(\lambda \varepsilon - \phi(\lambda))} \\ &= e^{-\phi^*(\varepsilon)} \end{align*} \end{equation}$$

因此，最优 Chernoff 界得证。$\square$

1.14 Hoeffding 不等式

设有 $m$ 个独立随机变量 $X_{i} \in [a_{i}, b_{i}]$，令 $\bar{X}$ 为 $X_{i}$ 的均值。Hoeffding 不等式表示：

$$\begin{equation} P(\bar{X} - \mathbb{E}[\bar{X}] \geq \varepsilon) \leq \exp (-\frac{2 m^{2} \varepsilon^{2}}{\sum_{i=1}^{m}(b_{i} - a_{i})^{2}}) \end{equation}$$

证明

首先，我们引入一个引理 (Hoeffding 定理)：

对于 $\mathbb{E}[X] = 0$ 且 $X \in [a, b]$ 的随机变量，对于任意 $\lambda \in \mathbb{R}$，有：

$$\begin{equation} \mathbb{E}[e^{\lambda X}] \leq \exp( \frac{\lambda^2(b-a)^2}{8} ) \end{equation}$$

由于 $e^x$ 是凸函数，对于任意 $x \in [a, b]$，可以写为：

$$\begin{equation} e^{\lambda x} \leq \frac{b-x}{b-a}e^{\lambda a} + \frac{x-a}{b-a}e^{\lambda b} \end{equation}$$

对上式取期望，得到：

$$\begin{equation} \mathbb{E}[e^{\lambda X}] \leq \frac{b-\mathbb{E}[X]}{b-a}e^{\lambda a} + \frac{\mathbb{E}[X]-a}{b-a}e^{\lambda b} = \frac{be^{\lambda a} - ae^{\lambda b}}{b - a} \end{equation}$$

记 $\theta = -\frac{a}{b-a}$，$h = \lambda(b-a)$，则：

$$\begin{equation} \frac{be^{\lambda a} - ae^{\lambda b}}{b - a} = [1-\theta + \theta e^{h}]e^{-\theta h} = e^{\ln(1-\theta + \theta e^{h})}e^{-\theta h} = e^{\ln(1-\theta + \theta e^{h}) -\theta h} \end{equation}$$

定义函数 $\varphi(\theta, h) = \ln(1-\theta + \theta e^{h}) -\theta h$。注意到 $\theta$ 实际上与 $h$ 无关。对 $h$ 求偏导数：

$$\begin{equation} \frac{\partial \varphi}{\partial h} = \frac{\theta e^h}{1 - \theta + \theta e^h} - \theta \end{equation}$$

显然有 $\frac{\partial \varphi}{\partial h}\big|_{h=0^+} = 0$。同理，利用链式法则可得：

$$\begin{equation} \frac{\partial^2 \varphi}{\partial h^2} = \frac{\theta e^h(1 - \theta + \theta e^h) - \theta^2e^{2h}}{(1 - \theta + \theta e^h)^2} = \frac{\theta e^h}{1 - \theta + \theta e^h}(1- \frac{\theta e^h}{1 - \theta + \theta e^h}) \leq \frac{1}{4} \end{equation}$$

根据泰勒展开式，可以得到：

$$\begin{equation} \varphi(\theta, h) \leq \frac{h^2}{8} = \frac{\lambda^2(b-a)^2}{8} \end{equation}$$

由 Markov 不等式可知，对于任意 $\lambda \gt 0$：

$$\begin{equation} P(\bar{X} - \mathbb{E}[\bar{X}] \geq \varepsilon) = P(e^{\lambda(\bar{X} - \mathbb{E}[\bar{X}])} \geq e^{\lambda \varepsilon}) \leq \frac{\mathbb{E}[e^{\lambda(\bar{X} - \mathbb{E}[\bar{X}])}]}{e^{\lambda \varepsilon}} \end{equation}$$

利用随机变量的独立性及 Hoeffding 引理，有：

$$\begin{equation} \frac{\mathbb{E}[e^{\lambda(\bar{X} - \mathbb{E}[\bar{X}]})]}{e^{\lambda \varepsilon}} = e^{-\lambda \varepsilon} \prod_{i=1}^{m} \mathbb{E}[e^{\lambda(X_{i} - \mathbb{E}[X_{i}]) / m}] \leq e^{-\lambda \varepsilon} \prod_{i=1}^{m} \exp (\frac{\lambda^{2}(b_{i} - a_{i})^{2}}{8 m^{2}}) \end{equation}$$

考虑二次函数 $g(\lambda) = -\lambda \varepsilon + \frac{\lambda^{2}}{8 m^{2}} \sum_{i=1}^{m}(b_{i} - a_{i})^{2}$，其最小值为 $-\frac{2 m^{2} \varepsilon^{2}}{\sum_{i=1}^{m}(b_{i} - a_{i})^{2}}$。

因此可以得到：

$$\begin{equation} P(\bar{X} - \mathbb{E}[\bar{X}] \geq \varepsilon) \leq \exp (-\frac{2 m^{2} \varepsilon^{2}}{\sum_{i=1}^{m}(b_{i} - a_{i})^{2}}) \end{equation}$$

$\square$

注意，这里并未要求随机变量同分布，因此Hoeffding 不等式常用来解释集成学习的基本原理。

1.15 McDiarmid 不等式

对于 $m$ 个独立随机变量 $X_{i} \in \mathcal{X}$，若函数 $f$ 是差有界的，则对于任意 $\varepsilon \gt 0$，有：

$$\begin{equation} P(f(X_{1}, \cdots, X_{m})-\mathbb{E}[f(X_{1}, \cdots, X_{m})] \geq \varepsilon) \leq \exp (-\frac{\varepsilon^{2}}{2 \sum_{i=1}^{m} c_{i}^{2}}) \end{equation}$$

证明

构造一个鞅差序列：

$$\begin{equation} D_j = \mathbb{E}[f(X) \mid X_1, \cdots, X_j] - \mathbb{E}[f(X) \mid X_1, \cdots, X_{j-1}] \end{equation}$$

容易验证：

$$\begin{equation} f(X) - \mathbb{E}[f(X)] = \sum_{i=1}^m D_i \end{equation}$$

由于 $f$ 是差有界的，因此满足 Azuma-Hoeffding 引理。代入后可得：

$$\begin{equation} P(f(X_1, \cdots, X_m) - \mathbb{E}[f(X_1, \cdots, X_m)] \geq \varepsilon) \leq \exp( -\frac{\varepsilon^2}{2\sum_{i=1}^m c_i^2} ) \end{equation}$$

原不等式得证。$\square$

1.16 Bennett 不等式

对于 $m$ 个独立随机变量 $X_{i}$，令 $\bar{X}$ 为 $X_{i}$ 的均值，若存在 $b \gt 0$，使得 $|X_i-\mathbb{E}[X_i]| \lt b$，则有：

$$\begin{equation} P(\bar{X}-\mathbb{E}[\bar{X}] \geq \varepsilon) \leq \exp (-\frac{m \varepsilon^{2}}{2(\sum_{i=1}^{m} \mathbb{V}[X_{i}] / m + b \varepsilon / 3)}) \end{equation}$$

证明

首先，Bennett 不等式是 Hoeffding 不等式的一个加强版，对于独立随机变量的条件可以放宽为弱独立条件，结论仍然成立。

这些 Bernstein 类的集中不等式更多地反映了在非渐近观点下的大数定律表现，即它们刻画了样本均值如何集中在总体均值附近。

如果将样本均值看作是样本（数据点的函数），即令 $f(X_{1}, \cdots, X_{m}) = \sum_{i=1}^{m} X_{i} / m$，那么 Bernstein 类不等式刻画了如下的概率：

$$\begin{equation} P(f(X_{1}, \cdots, X_{m}) - \mathbb{E}[f(X_{1}, \cdots, X_{m})] \geq \varepsilon) \end{equation}$$

为了在某些泛函上也具有类似 Bernstein 类的集中不等式形式，显然 $f$ 需要满足某些特定性质。差有界性是一种常见的约束条件。

定义 3: 差有界性

函数 $f: \mathcal{X}^{m} \rightarrow \mathbb{R}$ 满足对于每个 $i$，存在常数 $c_{i} \lt \infty$，使得：

$$\begin{equation} |f(x_{1}, \cdots, x_{i}, \cdots, x_{m})-f(x_{1}, \cdots, x_{i}^{\prime}, \cdots, x_{m})| \leq c_{i} \end{equation}$$

则称 $f$ 是差有界的。

为了证明这些结果，需要引入一些新的数学工具。

定义 4: 离散鞅

若离散随机变量序列（随机过程）$Z_m$ 满足：

1. $\mathbb{E}[|Z_{i}|] \lt \infty$
2. $\mathbb{E}[Z_{m+1} \mid Z_{1}, \cdots, Z_{m}] = \mathbb{E}[Z_{m+1} \mid \mathcal{F}_{m}] = Z_{m}$

则称序列 $Z_i$ 为离散鞅。

引理 2: Azuma-Hoeffding 定理

对于鞅 $Z_{i}$，若 $\mathbb{E}[Z_{i}] = \mu, Z_{1} = \mu_{\circ}$，则构造鞅差序列 $X_{i} = Z_{i} - Z_{i-1}$，且 $|X_{i}| \leq c_{i}$，则对于任意 $\varepsilon \gt 0$，有：

$$\begin{equation} P(Z_{m}-\mu \geq \varepsilon) = P(\sum_{i=1}^{m} X_{i} \geq \varepsilon) \leq \exp (-\frac{\varepsilon^{2}}{2 \sum_{i=1}^{m} c_{i}^{2}}) \end{equation}$$

证明

首先，若 $\mathbb{E}[X \mid Y] = 0$，则有 $\forall \lambda \gt 0$：

$$\begin{equation} \mathbb{E}[e^{\lambda X} \mid Y] \leq \mathbb{E}[e^{\lambda X}] \end{equation}$$

因此，由恒等式 $\mathbb{E}[\mathbb{E}[X \mid Y]] = \mathbb{E}[X]$ 及 Chernoff 一般性技巧，对于任意 $\lambda \gt 0$：

$$\begin{equation} \begin{align*} P(Z_{m}-\mu \geq \varepsilon) &\geq e^{-\lambda \varepsilon} \mathbb{E}[e^{\lambda(Z_{m}-\mu)}] \\ & = e^{-\lambda \varepsilon} \mathbb{E}[\mathbb{E}[e^{\lambda(Z_{m}-\mu)} \mid \mathcal{F}_{m-1}]] \\ & = e^{-\lambda \varepsilon} \mathbb{E}[e^{\lambda(Z_{m-1}-\mu)}\mathbb{E}[e^{\lambda (Z_{m}-Z_{m-1})} \mid \mathcal{F}_{m-1}]] \end{align*} \end{equation}$$

由于 $\{X_{i}\}$ 是鞅差序列，因此 $\mathbb{E}[X_{m} \mid \mathcal{F}_{m-1}] = 0, \mathbb{E}[X_{i}] = 0$。再结合不等式 $\mathbb{E}[e^{\lambda X} \mid Y] \leq \mathbb{E}[e^{\lambda X}]$ 及 Hoeffding 引理，有：

$$\begin{equation} \begin{align*} P(Z_{m}-\mu \geq \varepsilon) & \leq e^{-\lambda \varepsilon} \mathbb{E}[e^{\lambda(Z_{m-1}-\mu)}] \mathbb{E}[e^{\lambda X_{n}}] \\ & \leq e^{-\lambda \varepsilon} \mathbb{E}[e^{\lambda(Z_{m-1}-\mu)}] \exp (\frac{\lambda^{2} c_{m}^{2}}{2}) \end{align*} \end{equation}$$

迭代上不等式可得：

$$\begin{equation} P(Z_{m}-\mu \geq \varepsilon) \leq e^{-\lambda \varepsilon} \prod_{i=1}^{m} \exp (\frac{\lambda^{2} c_{i}^{2}}{2}) \end{equation}$$

当 $\lambda = \frac{\varepsilon}{\sum_{i=1}^{m} c_{i}^{2}}$ 时，上式右端取得极小值：

$$\begin{equation} P(Z_{m}-\mu \geq \varepsilon) \leq \exp (-\frac{\varepsilon^{2}}{2 \sum_{i=1}^{m} c_{i}^{2}}) \end{equation}$$

原不等式得证。$\square$

1.17 Bernstein 不等式

考虑 $m$ 个独立同分布的随机变量 $X_i, i \in [m]$。令 $\bar{X} = \frac{\sum_{i=1}^{m} X_i}{m}$。若存在常数 $b > 0$，使得对所有 $k \geq 2$，第 $k$ 阶矩满足 $\mathbb{E}[|X_i|^k] \leq \frac{k! b^{k-2}}{2} \mathbb{V}[X_1]$，则该不等式成立：

$$\begin{equation} \mathbb{P}(\bar{X} \geq \mathbb{E}[\bar{X}] + \epsilon) \leq \exp\left(\frac{-m\epsilon^2}{2 \mathbb{V}[X_1] + 2b\epsilon}\right) \end{equation}$$

证明

首先，我们需要将矩条件（moment condition）转换为亚指数条件（sub-exponential condition），以便进一步推导，即：

• 矩条件： 对于随机变量 $X$，其 $k$-阶中心矩 满足如下条件：

  $$\begin{equation} \mathbb{E}\left[|X - \mathbb{E}[X]|^k\right] \leq \frac{k! \, b^{k-2}}{2} \, \mathbb{V}[X], \quad \forall k \geq 2 \end{equation}$$

  其中：

  1. 中心矩：随机变量 $X$ 的 $k$ 阶中心矩为 $\mathbb{E}\left[|X - \mathbb{E}[X]|^k\right]$，表示 $X$ 偏离其期望值的 $k$ 次幂的期望值。中心矩用于衡量随机变量的分布形状，尤其是描述其尾部行为。当 $k = 2$ 时，中心矩即为随机变量的方差。
  2. $\frac{k!}{2}$ 是阶乘项，随着 $k$ 增大迅速增长。
  3. $b^{k-2}$ 是一个修正因子，其中 $b$ 为常数，用以控制高阶矩的增长速率。
  4. $\mathbb{V}[X]$ 表示随机变量 $X$ 的方差，它作为标准的离散度量来标定中心矩的大小。

• 亚指数条件： 给定随机变量 $X$，其均值为 $\mathbb{E}[X]$，方差为 $\mathbb{V}[X]$，则其偏离均值的随机变量 $X - \mathbb{E}[X]$ 的矩母函数（MGF）满足如下不等式：

  $$\begin{equation} \mathbb{E}\left[e^{\lambda (X - \mathbb{E}[X])}\right] \leq \exp\left(\frac{\mathbb{V}[X] \lambda^2}{2(1 - b\lambda)}\right), \quad \forall \lambda \in \left[0, \frac{1}{b}\right) \end{equation}$$

  其中：

  1. 矩母函数：这是一个重要的工具，用于控制随机变量的尾部概率。矩母函数的形式是 $\mathbb{E}[e^{\lambda X}]$，它通过调整 $\lambda$ 来捕捉不同程度的偏差行为。
  2. 方差主导项：不等式右边的表达式包含一个方差主导的项 $\frac{\mathbb{V}[X] \lambda^2}{2}$，类似于高斯分布的尾部特性，表明当 $\lambda$ 较小时，$X$ 的偏差行为主要由其方差控制，尾部概率呈现指数衰减。
  3. 修正项 $(1 - b\lambda)$：该项显示，当 $\lambda$ 接近 $\frac{1}{b}$ 时，尾部偏差的控制变得更加复杂。这种形式通常出现在亚指数条件中，意味着随机变量的尾部行为介于高斯分布和重尾分布之间，尾部衰减较慢但仍比重尾分布快。

• 步骤 1：中心化随机变量

设：

$$\begin{equation} Y = X - \mathbb{E}[X] \end{equation}$$

我们的目标是对 $Y$ 的矩母函数（MGF）进行上界：

$$\begin{equation} \mathbb{E}\left[e^{\lambda Y}\right] \end{equation}$$

• 步骤 2：展开指数矩

将 MGF 展开为幂级数（Taylor展开）：

$$\begin{equation} \mathbb{E}\left[e^{\lambda Y}\right] = \mathbb{E}\left[\sum_{k=0}^\infty \frac{(\lambda Y)^k}{k!}\right] = \sum_{k=0}^\infty \frac{\lambda^k}{k!} \mathbb{E}[Y^k] \end{equation}$$

由于 $\mathbb{E}[Y] = 0$，故 $k = 1$ 项消失：

$$\begin{equation} \mathbb{E}\left[e^{\lambda Y}\right] = 1 + \sum_{k=2}^\infty \frac{\lambda^k}{k!} \mathbb{E}[Y^k] \end{equation}$$

• 步骤 3：使用矩条件对中心矩进行上界

根据矩条件：

$$\begin{equation} \mathbb{E}\left[|Y|^k\right] \leq \frac{k! \, b^{k-2}}{2} \, \mathbb{V}[X] \end{equation}$$

因此：

$$\begin{equation} |\mathbb{E}[Y^k]| \leq \mathbb{E}\left[|Y|^k\right] \leq \frac{k! \, b^{k-2}}{2} \, \mathbb{V}[X] \end{equation}$$

• 步骤 4：代入 MGF 展开式

将上界代入 MGF 展开式：

$$\begin{equation} \mathbb{E}\left[e^{\lambda Y}\right] \leq 1 + \sum_{k=2}^\infty \frac{\lambda^k}{k!} \cdot \frac{k! \, b^{k-2}}{2} \, \mathbb{V}[X] = 1 + \frac{\mathbb{V}[X]}{2} \sum_{k=2}^\infty (b\lambda)^{k-2} \lambda^2 \end{equation}$$

通过令 $j = k - 2$ 进行简化：

$$\begin{equation} \mathbb{E}\left[e^{\lambda Y}\right] \leq 1 + \frac{\mathbb{V}[X] \lambda^2}{2} \sum_{j=0}^\infty (b\lambda)^j \end{equation}$$

• 步骤 5：求解几何级数的和

当 $b\lambda < 1$ 时，几何级数收敛：

$$\begin{equation} \sum_{j=0}^\infty (b\lambda)^j = \frac{1}{1 - b\lambda} \end{equation}$$